#include<iostream>
using namespace std;
struct FlistNode
{
	int val;
	FlistNode *next;
	FlistNode(const int x) :val(x), next(0){}
};
//剑指offer题16：输入两个单调递增的单链表，输出合并后的链表，使之满足单调不减规则。
FlistNode *MergeTwoSinglyList(FlistNode *head1, FlistNode *head2)
{
	if (!head1)return head2;//head1为空，直接返回head2
	if (!head2)return head1;//同理
	
	FlistNode *sma = head1, *big = head2;
	if (sma->val > big->val){ swap(sma, big); head1 = sma; }
	
	while (sma && big)//由于上面的操作，small->_val一定小于big->_val；
	{
		FlistNode *next;
		
		while (sma->next && sma->next->val <= big->val)
		sma = sma->next;//找到合适的位置
		
		next = big->next;
		
		big->next = sma->next;
		sma->next = big;
		
		sma = sma->next;//且在循环中一直保证small->_val小于big->_val.
		big = next;
	}
	return head1;
}
int main()
{
	FlistNode* head1 = new FlistNode(1);
	FlistNode* head2 = new FlistNode(1); head1->next = head2;
	FlistNode* head3 = new FlistNode(1); head2->next = head3;
	FlistNode* head4 = new FlistNode(4); head3->next = head4;
	FlistNode* head5 = new FlistNode(5); head4->next = head5;
	FlistNode* head6 = new FlistNode(6); head5->next = head6;
	
	FlistNode* cur1 = new FlistNode(1);
	FlistNode* cur2 = new FlistNode(2); cur1->next = cur2;
	FlistNode* cur3 = new FlistNode(3); cur2->next = cur3;
	FlistNode* cur4 = new FlistNode(4); cur3->next = cur4;
	FlistNode* cur5 = new FlistNode(5); cur4->next = cur5;
	FlistNode* cur6 = new FlistNode(6); cur5->next = cur6;
	
	FlistNode *tmp = MergeTwoSinglyList(head1, cur1);
	while (tmp)
	{
		cout << tmp->val << " ";
		tmp = tmp->next;
	}cout << endl;

	return 0;
}
